Regret bound

Choose $\mathbf{x}^{(1)},…,\mathbf{x}^{(T)}$ so that: $$\sum_{i=1}^T f_i (\mathbf{x}^{(i)}) \leq \left[\min_\mathbf{x} \sum_{i=1}^T f_i (\mathbf{x})\right] + \epsilon$$

Here $\epsilon$ is called the regret of our solution sequence $\mathbf{x}^{(1)},…,\mathbf{x}^{(T)}$. Regret compares to the best fixed solution in hindsight.

We typically $\epsilon$ to be growing sublinearly in $T$.

• Either $f_1, . . . , f_T$ are similar or changing slowly, so we can learn predict $f_i$ from earlier functions.
• Or $f_1, . . . , f_T$ are very different, in which case $\min_x \sum_{i=1}^T f_i(x)$ is large, so regret bound is easy to achieve.
• Or we live somewhere in the middle.

#incomplete ****

Online regret bound

References:

1. http://sbubeck.com/LecturesALL_Bubeck.pdf
2. https://www.jmlr.org/papers/volume11/jaksch10a/jaksch10a.pdf
3. https://arxiv.org/abs/2206.04640
4. https://datascience.stackexchange.com/questions/62141/what-are-regret-bounds
5. https://cs.adelaide.edu.au/~javen/talk/bounds_slide5.pdf